pub fn dp_rec_mc(amount: u32) -> u32 {
    return min_change(amount as u64).0 as u32;
}

fn min_change(amount: u64) -> (usize, Vec<usize>) {
    // 纸币面额，从大到小排序
    let denominations = [100, 50, 30, 20, 10, 5, 2, 1];
    // 用于记录每种面额纸币的数量，初始化为0
    let mut count = vec![0; denominations.len()];
    let mut remaining_amount = amount;

    // 贪心算法：从最大面额开始尝试找零
    for (i, denomination) in denominations.iter().enumerate() {
        while remaining_amount >= *denomination {
            count[i] += 1; // 使用一张该面额的纸币
            remaining_amount -= *denomination; // 更新剩余金额
        }
    }

    // 计算总纸币数
    let total_count = count.iter().sum::<usize>();

    (total_count, count)
}